package exercises.newcoder.solution;

/**
 * <a href="https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6?tpId=13&&tqId=11163&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking">
 * JZ10 矩形覆盖</a>
 *
 * <img src="https://uploadfiles.nowcoder.com/images/20201028/59_1603852524038_7FBC41C976CACE07CB222C3B890A0995">
 *
 * @author or2
 * @Description 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，从同一个方向看总共有多少种不同的方法？
 * <p>
 * 比如n=3时，2*3的矩形块有3种不同的覆盖方法(从同一个方向看)：
 * @create 2021年09月09日 时间: 16:28
 */
public class RectCover {
    public int rectCover(int target) {
        if (target < 0) {
            return 0;
        }
        switch (target) {
            case 1:
                return 1;
            case 2:
                return 2;
        }

        int[] ans = new int[target];
        ans[0] = 1;
        ans[1] = 2;
        for (int i = 2; i < target; i++) {
            ans[i] = ans[i - 1] + ans[i - 2];
        }

        return ans[target - 1];
    }
}
